package leetcode.editor.vscdev.backtracking;

import java.util.ArrayList;
import java.util.List;

import leetcode.editor.utils.*;

public class lc216 {
    public static void main(String[] args) {
        lc216 instance = new lc216(); // 创建外部类实例
        Solution solution = instance.new Solution(); // 通过外部类实例创建内部类对象
        List<List<Integer>> ans = solution.combinationSum3(9, 45);
        System.out.println(ans);
    }

    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            // 开始递归
            backtracking(n, k, 1);
            return res;
        }

        public void backtracking(int tar, int k, int startIndex) {
            
            if (path.size() == k) {
                if (tar == 0) {
                    // 满足要求加入结果
                    res.add(new ArrayList<>(path));
                }
                return;
            }

            for (int i = startIndex; i <= 9; i++) {
                if (tar - i < 0) break; // 剪枝优化
                tar -= i;
                path.add(i);
                backtracking(tar, k, i + 1); // 递归
                tar += i;
                path.removeLast();
            }
        }
    }
}
